#include <stdio.h>
#include <stdlib.h>

typedef struct LNode *List;

struct LNode{
    int Data;
    List Next;
};

struct LNode L;
List Ptrl;

//按序号查找，找到后返回指向该结点的指针
List FindKth(int K, List Ptrl);
//按值查找，找到后返回指向该结点的指针
List Find(int X, List Ptrl);
List insert(int pos, int val, List Ptrl);
List delete(int i, List Ptrl);
void show(List Ptrl);
int length(List Ptrl);

int main(){
    printf("test\n");
    List p;
    p = insert(1, 1, Ptrl);
    p = insert(2, 2, p);
    p = insert(3, 3, p);

    p = delete(2,p);
    int len = length(p);
    printf("length = %d", len);

    show(p);
    return 0;  
}

List FindKth(int K, List Ptrl){
    List p = Ptrl;
    int i = 1;
    while(p!=NULL && i<K){
        p = p->Next;
        i++;
    }
    if(i == K){
        //找到了第K个，返回指针
        return p;
    }else{
        return NULL;
    }
}

List Find(int X, List Ptrl){
    List p = Ptrl;
    while(p!=NULL && p->Data !=X){
        p = p->Next;       
    }
    return p;
}

List insert(int i, int X, List Ptrl){
    List p,s;
    //链表新增时表头属于特殊位置，要单独讨论
    if(i==1){
        s = (List)malloc(sizeof(struct LNode));
        s->Data = X;
        //s指向头结点
        s->Next = Ptrl;
        return s;
    }
    //找到第i-1个结点（即待插入结点的位置）
    p = FindKth(i-1, Ptrl);
    //不插在首位时可能出现由于插入位置的参数超过链表长度的情况，这是p=NULL
    if(p == NULL){
        printf("插入位置错误");
        return NULL;
    }else{
        //表示此位置可以插入
        s = (List)malloc(sizeof(struct LNode));
        s->Data = X;
        s->Next = p->Next;
        p->Next = s;
        return Ptrl;
    }
};

List delete(int i, List Ptrl){
    List p,s;
    //链表删除时表头也属于特殊位置，要单独讨论
    if(i==1){
        s = Ptrl;
        if(Ptrl == NULL){
            //说明头结点为空即链表为空
            printf("链表为空，无法删除");
            return NULL;
        }else{
            Ptrl = Ptrl->Next;
            free(s);
            return Ptrl;
        }
    }
    //找到待删除结点的前一个结点
    p = FindKth(i-1, Ptrl);
    //这里注意：进行删除操作时，待删除结点和待删除结点的前一个结点都不能为空
    if(p==NULL){
        printf("第%d个结点不存在\n", i-1);
        return NULL;
    }else if(p->Next == NULL){
        printf("第%d个结点不存在\n", i);
        return NULL;
    }else{
        //两结点都存在
        s = p->Next;
        p->Next = s->Next;
        free(s);
        return Ptrl;
    }
};

void show(List Ptrl){
    List p = Ptrl;
    printf("show:");
    while(p != NULL){
        printf(" %d ", p->Data);
        p = p->Next;        
    }
    printf("\n");
};

int length(List Ptrl){
    List p = Ptrl;
    int len = 0;
    while(p != NULL){
        p = p->Next;
        len++;
    }
    return len;
};